function [split_point, min_entropy] = id3_find_split(interval, label)
%CALC_ENTROPY Summary of this function goes here
%   Detailed explanation goes here
    epoint = sort(unique([interval(:, 1)', interval(:,2)']));
    weight = interval(:, 2) - interval(:, 1);
    weight = ones ./weight;
 
    split_point = -100;
    min_entropy = 100000;  
    M = size(epoint, 2);
    N = size(interval, 1);
 
    min_label = min(label);
    max_label = max(label);
    set(0,'DefaultAxesColorOrder',[1,0,0;0,1,0;0,0,1], 'DefaultAxesLineStyleOrder','-|-.|--|:');
    plotdata = zeros(50, M-1);
    for i = 1 : M-1
        left = epoint(i);
        right = epoint(i+1);
        
        L = 0;
        R = 0;
        W = 0;
        for k = 1 : size(interval, 1)
            if (interval(k, 2) <= left) 
                L = L+1;
            elseif (interval(k,2) > left && interval(k,1) <= left)
                L = L+weight(k)*(left-interval(k,1));
                W = W+weight(k);                   
                R = R+weight(k)*(interval(k,2)-left);
                if (weight(k)*(right-left) > weight(k)*(interval(k,2)-left))
                    disp('ALERT');
                    disp([interval(k,1), interval(k,2)]);
                    disp([left, right, weight(k)]);
                end                    
            elseif (interval(k,1) > left )
                R = R+1;
            end
        end
        Li = zeros([max_label, 1]);
        Ri = zeros([max_label, 1]);
        Wi = zeros([max_label, 1]);
        
        for j = min_label : max_label
            interval_j = interval(label == j, :);
            weight_j = weight(label == j);            
            Li(j) = 0;
            Wi(j) = 0;
            Ri(j) = 0;
            for k = 1 : size(interval_j, 1)
                if (interval_j(k, 2) <= left) 
                    Li(j) = Li(j)+1;
                elseif (interval_j(k,2) > left && interval_j(k,1) <= left)
                    Li(j) = Li(j)+weight_j(k)*(left-interval_j(k,1));
                    Wi(j) = Wi(j)+weight_j(k);                   
                    Ri(j) = Ri(j)+weight_j(k)*(interval_j(k,2)-left);
                    if (weight_j(k)*(right-left) > weight_j(k)*(interval_j(k,2)-left))
                        disp('ALERT');
                        disp([interval_j(k,1), interval_j(k,2)]);
                        disp([left, right, weight_j(k)]);
                    end                    
                elseif (interval_j(k,1) > left )
                    Ri(j) = Ri(j)+1;
                end
            end
            if (Ri(j) < Wi(j)*(right-left))
                disp('ERROR');
                disp([Ri(j), Wi(j)*(right-left), right-left, Wi(j)]);
            end
        end
        [min_x, entropy, entropyA, entropyB, result] = find_min(L*ones([max_label, 1]), R*ones([max_label, 1]), W*ones([max_label, 1]), Li, Ri, Wi, right-left);
        if (min_x > right-left) 
            entropy = entropyB;
            min_x = right-left;
        elseif (min_x < 0)
            entropy = entropyA;
            min_x = 0;
        end
        
        if (entropy < min_entropy) 
            split_point = min_x+left;
            min_entropy = entropy;
        end
        axe = (i-1)*50: i*50;
     %   disp(result);
        plotaxe(:, i) = ((1:50) * (right-left)/50 + ones([1, 50])*left)';
        plotdata(:, i) = result';
%        for j = 1 : 50
%            plotdata((i-1)*50+j, i) = result(j);
%        end

    end    
%    plot(plotaxe, plotdata);

end 



function [min_x, min_entropy, entropyA, entropyB, result] = find_min(L, R, W, Li, Ri, Wi, maxX) 
    epsilon = 0.00000001*ones(size(L));
    function d = dentropy_dx(x)      
        left = 0;
        right = 0;
        for i = 1 : size(Li, 1)
            if (Li(i)+Wi(i)*x > 0 && L(1)+W(1)*x > 0)
                left = left + Wi(i)*log((Li(i)+Wi(i)*x)/(L(1)+W(1)*x)) + Wi(i) - (Li(i)+Wi(i)*x) * W(1) / (L(1)+W(1)*x);               
            end
            if (Ri(i)-Wi(i)*x > 0 && R(1)-W(1)*x > 0)
                right = right - Wi(i)*log((Ri(i) - Wi(i)*x)/(R(1)-W(1)*x)) - Wi(i) + (Ri(i)-Wi(i)*x) * W(1) / (R(1)-W(1)*x);
            end


            if (Ri(i)-Wi(i)*x < 0 && x < maxX)
                disp('Error');
                disp([Ri(i), Wi(i)*x, x, i]);
            end

        end       
%        (Ri-Wi*x).*(-Wi./(Ri-Wi*x)+W./(R-W*x));
        d = left+right;
    end
    
    function e = entropy_x(x)
        left = 0;
        right = 0;
        for i = 1 : size(Li, 1)
            if (Li(i)+Wi(i)*x ~= 0 && L(1)+W(1)*x ~= 0)
                left = left + (Li(i)+Wi(i)*x)*log( (Li(i) + Wi(i)*x) / (L(1)+W(1)*x));
            end
            if (Ri(i)-Wi(i)*x ~= 0 && R(1)-W(1)*x ~= 0)
                right = right + (Ri(i)-Wi(i)*x) *log( (Ri(i)-Wi(i)*x)/(R(1)-W(1)*x));
            end
%            disp([left, right]);
        end
        e = -left - right;
       
    end    
    
%    min_x = fzero(@dentropy_dx, 0);
    min_x_2 = fminbnd(@entropy_x, 0, maxX);
    
%    min_entropy = entropy_x(min_x);
    min_entropy_2 = entropy_x(min_x_2);
    
    entropyA = entropy_x(0);
    entropyB = entropy_x(maxX);
        
%    if (abs(min_x_2-0) > 0.0001 && abs(min_x_2-maxX) > 0.00001) 
%        disp('Error');
%        subplot(2,1,1);
%        fplot(@entropy_x, [0, maxX]);        
%       subplot(2,1,2);
%       fplot(@dentropy_dx, [0, maxX]);             
%        disp(maxX);
%        disp([min_entropy, min_x]);
%       disp([min_entropy_2, min_x_2]);        
     
%    end

    result = zeros(1, 50);
    index = 1;
    for x = 1: 50
        result(index)  = entropy_x(x*maxX/50);
%        disp([result(index), x*maxX/50]);
        index = index+1;
    end    
    
    min_x = min_x_2;
    min_entropy = min_entropy_2;
end